package com.markus.code.有序表;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/29 11:40
 * todo: 手写一个LRU缓存机制的数据结构
 */
public class LRUCacheDemo {
    /**
     * 封装一个节点
     */
    public static class Node<K,V>{
        K key;
        V value;
        Node last;
        Node next;
        public Node(K k,V v){
            key = k;
            value = v;
            last = null;
            next = null;
        }
    }
    /**
     * 设计一个双端队列
     */
    public static class DirectDoubleLinkedList<K,V>{
        Node<K,V> head;
        Node<K,V> tail;
        public DirectDoubleLinkedList(){
            head = null;
            tail = null;
        }
        public void addNode(Node newNode){
            //判断头是否为空,如果为空的话说明此时双端队列中还没有节点
            if (head == null){
                head = newNode;
                tail = newNode;
            }else{
                //否则就是队列中已经有节点了
                tail.next = newNode;
                newNode.last = tail;
                tail = newNode;
            }
        }
        public void moveNodeToTail(Node node){
            //当前节点已经是尾节点
            if (tail == node){
                return;
            }
            if (head == node){
                head = node.next;
                head.last = null;
            }else{
                //中间节点
                node.last.next = node.next;
                node.next.last = node.last;
            }
            node.next = null;
            tail.next = node;
            node.last = tail;
            tail = node;
        }
        public Node<K,V> removeHead(){
            if (head == null){
                return null;
            }
            Node<K,V> res = head;
            if (head == tail){
                //链表中只有一个节点的时候
                head = null;
                tail = null;
            }else{
                //链表中不只有一个节点的时候
                head = res.next;
                res.next = null;
                head.last = null;
            }
            return res;
        }
    }
    /**
     * 设计一个LRU缓存结构
     */
    public static class LRUCache<K,V>{
        private HashMap<K,Node<K,V>> nodeMap;
        private DirectDoubleLinkedList<K,V> nodeList;
        private int capacity;
        public LRUCache(int cap){
            if (cap < 1){
                throw new RuntimeException("缓存的大小必须大于0");
            }
            nodeMap = new HashMap<>();
            nodeList = new DirectDoubleLinkedList();
            capacity = cap;
        }
        public V get(K k){
            //首先要确保有这个节点
            if (nodeMap.containsKey(k)){
                Node<K, V> kvNode = nodeMap.get(k);
                nodeList.moveNodeToTail(kvNode);
                return kvNode.value;
            }
            return null;
        }
        public void put(K k,V v){
            //如果map中存在这个节点，那就是更新
            if (nodeMap.containsKey(k)){
                Node<K,V> node = nodeMap.get(k);
                node.value = v;
                nodeList.moveNodeToTail(node);
            }else{
                //map中不包含这个节点，就直接插入,这个时候有可能出现替换的情况
                Node<K,V> node = new Node(k,v);
                nodeList.addNode(node);
                nodeMap.put(k,node);
                if (nodeMap.size() == capacity+1){
                    removeCache();
                }
            }
        }
        private void removeCache(){
            Node<K, V> kvNode = nodeList.removeHead();
            nodeMap.remove(kvNode.key);
        }
    }

    public static void main(String[] args) {
//        LRUCacheDemo demo = new LRUCacheDemo();
//        LRUCache<String,Integer> testCache = new LRUCache<>(3);
//        testCache.put("A", 1);
//        testCache.put("B", 2);
//        testCache.put("C", 3);
//        System.out.println(testCache.get("B"));
//        System.out.println(testCache.get("A"));
//        testCache.put("D", 4);
//        System.out.println(testCache.get("D"));
//        System.out.println(testCache.get("C"));
        LRUCache<Integer,Integer> cache = new LRUCache<>(2);
        cache.put(1, 1);
        cache.put(2, 2);
        // 返回  1
        System.out.println(cache.get(1));
        // 该操作会使得关键字 2 作废
        cache.put(3, 3);
        // 返回 -1 (未找到)
        System.out.println(cache.get(2));
        // 该操作会使得关键字 1 作废
        cache.put(4, 4);
        // 返回 -1 (未找到)
        System.out.println(cache.get(1));
        // 返回  3
        System.out.println(cache.get(3));
        // 返回  4
        System.out.println(cache.get(4));
    }
}
